package main

type ListNode struct {
	Val  int
	Next *ListNode
}

/**
 *
 * @param head ListNode类
 * @return void
 */
func reorderList(head *ListNode) {
	// write code here
	solve(0, head)

}

func solve(i int, head *ListNode) (rj int, rtail *ListNode) {
	if head == nil {
		return -1, nil
	}
	j, tail := solve(i+1, head.Next)
	rj = j + 1
	if i == j {
		rtail = tail.Next
		tail.Next = nil
		head.Next = tail
	} else if i == j+1 {
		head.Next = nil
		rtail = tail
	} else if i < j {
		rtail = tail.Next
		tail.Next = head.Next
		head.Next = tail
	} else {
		rtail = head
	}
	return
}
